package com.simonf.divide_and_conquer;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: smionf
 * @Date: 2024/03/04/20:48
 * @Description:
 */

/**
 * @Description: 解法不如动态规划,LeeCode判超时
 * @Param:
 * @return:
 * @Author: simonf
 * @Date: 2024/3/4
 */
public class LC53MaxSubArray {
    public int maxSubArray(int[] nums) {

        /**
         * @Description: 分为两边取最大值
         */
        return maxSubArray(nums, 0, nums.length - 1);
    }

    public int maxSubArray(int[] nums, int start, int end) {

        if (start >= end) {
            return nums[start];
        }

        int mid = (start + end) / 2;

        /**
         * @Description: 左边取最大值
         */
        int leftMax = maxSubArray(nums, start, mid);

        /**
         * @Description: 右边取最大值
         */
        int rightMax = maxSubArray(nums, mid + 1, end);

        int crossMax = getcrossMAX(nums, start, mid, end);

        return Math.max((Math.max(leftMax, rightMax)), crossMax);

    }

    private int getcrossMAX(int[] nums, int start, int mid, int end) {
        int leftSum = nums[mid];
        int leftSumMax = leftSum;
        for (int i = mid - 1; i >= 0; i--) {
            leftSum += nums[i];
            if (leftSum > leftSumMax) {
                leftSumMax = leftSum;
            }
        }

        int rightSum = nums[mid + 1];
        int rightSumMax = rightSum;
        
        /**
        * @Description:mid索引已经包含在左边的部分，向右扩展时，需要从mid + 1开始，如果索引起始为mid + 1，会导致重复计算索引元素，所以需要将索引设置为mid + 2
         *
        */
        for (int i = mid + 2; i <= end; i++) {
            rightSum += nums[i];
            if (rightSum > rightSumMax) {
                rightSumMax = rightSum;
            }
        }
        return leftSumMax + rightSumMax;
    }

}
